import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[]nums = {1,9,2,8,3,7,4,6,5};
        //insertSort(nums);
        //shell(nums);
        //quickSort(nums,0,nums.length-1);
        mergeSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

    private static void mergeSort(int[] nums, int left, int right) {
        if(left>=right)
            return;
        int mid = left+(right-left)/2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        int[]tmp = new int[nums.length];
        int i = left;
        int k = 0;
        int j = mid+1;
        while(i<=mid&&j<=right){
            if(nums[i]<nums[j]){
                tmp[k++] = nums[i++];
            }else{
                tmp[k++] = nums[j++];
            }
        }
        while (i<=mid){
            tmp[k++] = nums[i++];
        }
        while(j<=right){
            tmp[k++] = nums[j++];
        }
        for (int l = left; l <= right; l++) {
            nums[l] = tmp[l-left];
        }


    }

    private static void quickSort(int[] nums, int left, int right) {
        if(left>right)
             return;
        int pivot = partition(nums,left,right);
        quickSort(nums,left,pivot-1);
        quickSort(nums,pivot+1,right);
    }

    private static int partition(int[] nums, int left, int right) {
        int key = nums[left];
        int i = left;
        while(left<right){
            while (left<right&&nums[right]>=key){
               right--;
            }
            while (left<right&&nums[left]<=key){
              left++;
            }
            swap(nums,left,right);
        }
        swap(nums,left,i);
        return left;
    }

    private static void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}
